package com.zang.tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author ZVerify
 * @see <a href="https://leetcode.cn/problems/merge-two-binary-trees/">...</a>
 * @since 2022/11/01 11:18
 **/
public class 合并二叉树 {

    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1==null) return root2;
        if(root2==null) return root1;
        Deque<TreeNode> list = new LinkedList<>();
        list.addLast(root1);
        list.addLast(root2);
        while (!list.isEmpty()) {
            TreeNode left = list.pollFirst();
            TreeNode right = list.pollFirst();
            // 合并当前节点
            left.val = left.val + right.val;
            // 两个左都不为null，去下一层进行计算
            if (left.left != null && right.left != null) {
                list.addLast(left.left);
                list.addLast(right.left);
            }
            // 两个右都不为null，去下一层进行计算
            if (left.right != null && right.right != null) {
                list.addLast(left.right);
                list.addLast(right.right);
            }
            // 左边的左节点为null，右边的左不为null，直接替换，否则为当前值
            if (left.left == null && right.left != null) {
                left.left = right.left;
            }
            // 左边的右节点为null，右边的右不为null，直接替换，否则为当前值
            if (left.right == null && right.right != null) {
                left.right = right.right;
            }
        }
        return root1;
    }
}
